//474 Ones and Zeroes
/*
给定 m 个数字 0 和 n 个数字 1，以及一些由 0-1 构成的字符串，求利用这些数字最多可以构
成多少个给定的字符串，字符串只可以构成一次

输入输出样例
	输入两个整数 m 和 n，表示 0 和 1 的数量，以及一个一维字符串数组，表示待构成的字符串；
	输出是一个整数，表示最多可以生成的字符串个数

Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4

在这个样例中，我们可以用 5 个 0 和 3 个 1 构成 [“10” , “0001” , “1” , “0” ]

*/
// 主函数
int findMaxForm(vector<string> &strs, int m, int n)
{
	vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
	for (const string &str : strs)
	{
		auto [count0, count1] = count(str);
		for (int i = m; i >= count0; --i)
		{
			for (int j = n; j >= count1; --j)
			{
				dp[i][j] = max(dp[i][j], 1 + dp[i - count0][j - count1]);
			}
		}
	}
	return dp[m][n];
}
// 辅函数
pair<int, int> count(const string &s)
{
	int count0 = s.length(), count1 = 0;
	for (const char &c : s)
	{
		if (c == '1')
		{
			++count1;
			--count0;
		}
	}
	return make_pair(count0, count1);
}
